COMMENT ⊗   VALID 00013 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	  Data structures, GSINIT
C00006 00003	  UNLINK, NEWCEL
C00009 00004	  NXTTIM
C00010 00005	  INVLDT, INVLR0
C00012 00006	  CHANGE, CHNGER
C00018 00007	  ADDCHG
C00020 00008	  GETVAL, GETVR0
C00022 00009	  EVALND, EVLEXP
C00030 00010	  MAKEXP, ADDCLC, REMCLC, DELEXP
C00038 00011	  MAKEVN, DELVN
C00045 00012	  MGNDS  marking method for gnodes
C00059 00013	  Known Bugs
C00062 ENDMK
C⊗;
;  Data structures, GSINIT

.SBTTL Graph routines.
;Graph structure definitions
;RHT 9/74  RF 6/75, 10/75

COMMENT ⊗  
This is the runtime's prime evil,
The murderous graph nodes and interlocks.
⊗

;GRAPH NODES		;Common fields for Variables and Expressions
	II==0
	XX  GNMODE	;Mode bits.  1:variable. 2:expression
	XX  NXTGN	;Links all graph nodes.  Points to next one.
	XX  PRVGN	;Previous link in that chain
	XX  INVMRK	;0 => valid, other => invalid
	XX  GNVAL	;points at the value cell
	XX  GNDEPS	;list of dependents (variables or expressions)
	GNEND==II	;marks the end of the common region

;VARIABLE NODES		;Explicitly released, formed from large block store.
	II==GNEND
	XX  VALIDF	;a count which is incremented at every reevaluation
	XX  VNCLCS	;list of expression nodes used as calculators
	XX  VNCHGS	;list of change cells. (see format below)
	VNDSIZ == II/2	;Length of variable node (in words)

;EXPRESSION NODES	;Explicitly released, formed from large block store.
	II==GNEND
	XX  ENISB	;the ISB for this expression
	XX  ENIPC	;the IPC for this expression
	XX  ENNEED	;list of needed nodes (cell-linked)
	ENDSIZ == II/2	;Length of expression node (in words)

;CELL LINKS
	II==0
	XX  CAR	
	XX  CDR	

;CHANGER CELL		;Explicitly released, formed from large block store.
	II==0
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
	CHGCSZ == II/2	;Size of changer cell, in words

GNODES:  .BLKW 1	;head of chain of graph nodes.
TIME:	0		;used during evaluation of nodes
VALIDNO:0		;used for validity field of nodes
GNEVT:	.BLKW 1		;event for interlocking graph references

GSINIT:
;Initialize the graph structure to a null situation;
	EVMAK	;Make a new interlock event.
	MOV (SP),GNEVT;
	EVSIG 	;Give it one signal.
	CLR GNODES;
	CLR TIME;
	CLR VALIDNO;
	RTS PC	;Done

;  UNLINK, NEWCEL

UNLINK:
COMMENT ⊗ A list is in R0, and an entity in R1.  All occurrences of
that entity, if any, are removed from the list.  The orphaned cells
are left for the garbage collector.  A pointer to the list is
returned in R0 (it has changed if the first element was deleted).  ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV R0,R2		;R2 ← forward pointer
	BEQ 3$			;If no list, then done
	MOV R1,-(SP)		;Save R1
	JSR PC,NEWCEL		;R0 ← dummy header  NOTE: don't end critical
				;section til return from UNLINK
	MOV (SP)+,R1		;Restore R1
	MOV R2,CDR(R0)		;Set up dummy header
	MOV R0,R3		;R3 ← backward pointer
1$:	CMP CAR(R2),R1		;Match?
	BEQ 4$			;Yes
	MOV R2,R3		;
2$:	MOV CDR(R2),R2		;Move along
	BNE 1$			;If any more
	MOV CDR(R0),R0		;Go past dummy
3$:	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Return
4$:	MOV CDR(R2),CDR(R3)	;Link past the orphan
	BR  2$			;Continue

NEWCEL:
COMMENT ⊗ Returns in R0 a pointer at a cell.  Taken from cell space
unless there is none.  Uses direct jumps, lets the subsidiary do the
return. ⊗
    .IFNZ SMALLB
	MOV #CELSPC,R0	;
	JMP GETSBK	;Allocate from small blocks
    .IFF
	MOV #2,R0	;Number of words needed
	JMP GTFREE	;R0 ← LOC[new block]
    .ENDC
;  NXTTIM

COMMENT ⊗
	JSR	PC,NXTTIM
 	
Returns TIME←TIME+1 in R0.  If TIME goes negative then set all
positive mark cells to negative, then set time to 1. ⊗


NXTTIM:	INC	TIME		;TIME←TIME+1
	MOV	TIME,R0
	BGT	4$		;OK?
	MOV	GNODES,R0	;
	BEQ	3$		;DID WE HAVE ANY??
1$:	TST	INVMRK(R0)	;YES
	BLE	2$		;WAS INVMRK POSITIVE
	NEG	INVMRK(R0)	;YES, NEGATE IT
2$:	MOV	NXTGN(R0),R0	;GO ON TO NEXT
	BNE	1$		;IF ANY
3$:	INC	R0		;R0←0+1
	MOV	R0,TIME		;TIME IS 1 AGAIN
4$:	RTS	PC

;  INVLDT, INVLR0

INVLDT:	
COMMENT ⊗ Called only from the outside world.  R0 is the node to
invalidate, along with all dependents.  We must invalidate dependents
even if the given node is already invalid, unless we have just now
invalidated it, which would imply that we are in a cycle.  ⊗
	EVWAIT	GNEVT		;We change TIME, so must lock this
	MOV	R0,R1
	JSR	PC,NXTTIM
	MOV	R1,R0
	JSR	PC,INVLR0
	EVSIG	GNEVT		;End of critical section
	RTS	PC

INVLR0:	CMP	INVMRK(R0),TIME	;Are we in a cycle?
	BEQ	4$		;Yes.  Return.
1$:	MOV	TIME,INVMRK(R0)	;No.  Invalidate this node.
	MOV	R2,-(SP)	;Save R2 for recursive call
	MOV	GNDEPS(R0),R2	;R2 ← list of dependents
	BEQ	3$		;If any 
2$:	MOV	CAR(R2),R0	;R0 ← next dependent
	JSR	PC,INVLR0	;Go Invalidate it.
	MOV	CDR(R2),R2	;Repeat for the rest
	BNE	2$		;If any
3$:	MOV	(SP)+,R2	;Restore R2
4$:	RTS	PC

;  CHANGE, CHNGER

COMMENT ⊗ Called by the outside world to put a new value, CHG.VNEW,
in the variable node CHG.ND.  Returns with CHG.ND in R0. ⊗

ROUTINE CHANGE,<CHG.ND,CHG.VNEW>
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	CHG.ND(RF),R1	;R1 ← the target node.
	EVWAIT	GNEVT		;Wait until OK to enter critical code.
	JSR	PC,NXTTIM	;
	MOV	R1,R0		;
	JSR	PC,INVLR0	;invalidate it for the nonce
	MOV	CHG.ND(RF),R0	;R0 ← the target node
	MOV	GNVAL(R0),R2	;R2 ← old value
	MOV	CHG.VNEW(RF),GNVAL(R0) ;stow the new value
	MOV	VNCHGS(R0),R3	;R3 ← list of changers
	BEQ	2$		;if any
	EVSIG	GNEVT		;Leave the overall graph node critical region.
1$:	JSR	PC,CHNGER	;Call the next change routine
	MOV	NXTCHG(R3),R3	;R3 ← next changer
	BNE	1$
	EVWAIT	GNEVT		;Enter critical section again.
2$:	MOV	CHG.ND(RF),R0	;R0 ← the target node
	CLR	INVMRK(R0)	;Revalidate it
	INC	VALIDNO		;A new validity number
	MOV	VALIDNO,VALIDF(R0)	;which is put in the validf
	EVSIG	GNEVT		;Ok for others to enter critical code now.
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	PC		;Return

CHNGER:
COMMENT ⊗ Calls the change routine indicated.  This is done by
instantiating a new interpreter to do the work.  It should terminate
the normal way, with a TERMINATE command.  R2 points to the old
value, and CHG.VNEW(RF) points to the new value.  R3 points to the
changer cell.  These values are put into the new ISB.  GNODE
exclusion should be released before the call to CHNGER.  Recall that
a changer cell looks like this:
	XX  NXTCHG	;next changer cell in chain
	XX  CHGISB	;Points to interpreter status block to resolve addressing
	XX  CHGIPC	;the interpeter PC where the calculation starts
⊗

	MOV R2,-(SP)	;Save R2
	MOV R3,-(SP)	;Save R3
	MOV R4,-(SP)	;Save R4

	;make a new interpreter to do the work
	MOV CHGISB(R3),R4	;R4 ← ISB we have to emulate
	MOV CHGIPC(R3),R0	;R0 ← IPC of new ISB
	EVMAK		;Stack a new event for communication with subsidiary
	MOV (SP),R1	;R1 ← copy of that event
	JSR PC,SPAWN	;R0 ← Process decriptor
	MOV PDBR4(R0),R4;R4 ← ISB of new interpreter
	MOV R2,OLDV(R4)	;Stow the "old value" pointer in environment.
	MOV CHG.VNEW(RF),NEWV(R4)	;Stow the "new value" pointer.
	FORK R0,#INTERP,#USRDM,#2 ;Cause the new process to be started at high prio.

	;clean up after the interpreter
	EVWAIT 		;Wait for the completion event (still on stack)

	MOV (SP)+,R4	;Restore R4
	MOV (SP)+,R3	;Restore R3
	MOV (SP)+,R2	;Restore R2
	RTS PC		;Done
;  ADDCHG

ROUTINE ADDCHG,<ACH.ND,ACH.CHG>
COMMENT ⊗ ACH.ND is the target graph node, and ACH.CHG is a changer
cell all prepared except for the link to the other changers.  It is
necessary to perform this linking.  ⊗
	MOV	R2,-(SP)	;Save R2
	MOV	ACH.ND(RF),R2	;R2 ← LOC[target node]
	MOV	ACH.CHG(RF),R1	;R1 ← LOC[changer cell]
	EVWAIT	GNEVT		;Enter critical region for graph nodes
	MOV	VNCHGS(R2),NXTCHG(R1) ;Link new changer into list
	MOV	R1,VNCHGS(R2)	;
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R2	;Restore R2
	RTS	PC		;Done
;  GETVAL, GETVR0

COMMENT ⊗ Called by the outside world.  Returns LOC[value(GTV.ND)] in
R0 and the VALIDF in R1, after having scrounged around to get a valid
value, if necessary and possible.  ⊗

ROUTINE GETVAL,<GTV.ND>
	MOV	GTV.ND(RF),R0
	JSR	PC,GETVR0
	RTS	PC

GETVR0:	TST	INVMRK(R0)	;Is the current value good?
	BEQ	1$		;Yes
	EVWAIT	GNEVT		;No.  Enter critical region.
	MOV	R0,-(SP)	;Save target node
	MOV	R0,-(SP)	;Stack it too - first arg to EVALND
	JSR	PC,NXTTIM	
	MOV	R0,-(SP)	;2nd arg - time
	MOV	RF,-(SP)	;Save RF
	MOV	SP,RF
	JSR	PC,EVALND	;CALL EVALND,<GTV.ND,TIME←TIME+1>
	MOV	(SP)+,RF	;Restore RF
	ADD	#4,SP		;Pop 2 args
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R0	;R0 ← target node, now validated
1$:	MOV	VALIDF(R0),R1	;Get the validity count
	MOV	GNVAL(R0),R0	;R0 ← value cell
	RTS	PC		;Done
;  EVALND, EVLEXP

COMMENT ⊗ EVALND is a recursive procedure, which is given EVL.ND, the
target node to evaluate, and EVL.T, the "time" of evaluation.  If
necessary, it calls itself at the same "time" to track down a chain
of related nodes.  GNEVT exclusion should be on before this routine
is first called, and will remain on after the return. ⊗

ROUTINE EVALND,<EVL.ND,EVL.T>
	MOV	EVL.ND(RF),R0	;R0 ← target graph node
	MOV	INVMRK(R0),R1	;Is the node already valid?
	BEQ	9$		;Yes
	CMP	R1,EVL.T(RF)	;No.  Have we already looked at it this "time"?
	BEQ	9$		;Yes
	MOV	EVL.T(RF),INVMRK(R0)	;No. We have touched our node now
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	BIT	#1,GNMODE(R0)	;A variable or an expression?
	BNE	1$		;Variable
	CALL	EVLEXP,<R0,EVL.T(RF)>	;Sets GNVAL and INVMRK correctly
	BR	8$		;Done

1$:	;evaluate a variable.
	MOV	VNCLCS(R0),R2	;R2 ← list of calculator expressions
	BEQ	8$		;if any
2$:	MOV	CAR(R2),R1	;R1 ← first expression
	TST	INVMRK(R1)	;Is this expression valid?
	BNE	3$		;No
	MOV	GNVAL(R1),GNVAL(R0)	;Yes.  Copy its value pointer
	BR	7$		;Success exit.
3$:	MOV	CDR(R2),R2	;R2 ← rest of expression list
	BNE	2$		;Try with next one.

	;no currently valid expression.  Try to evaluate one.
	MOV	VNCLCS(R0),R2	;R2 ← list of calculator expressions
	BEQ	8$		;if any
4$:	MOV	CAR(R2),R1	;R1 ← first expression
	CALL	EVALND,<R1,EVL.T(RF)>
	MOV	CAR(R2),R1	;
	TST	INVMRK(R1)	;Successfully evaluated?
	BEQ	5$		;Yes
	MOV	CDR(R2),R2	;Try next one
	BNE	4$		;If any
	BR	8$		;Give up
5$:	MOV	EVL.ND(RF),R0	;
	MOV	GNVAL(R1),GNVAL(R0)	;Transfer the value
	BR	7$		;Success return


COMMENT ⊗  Seems to be a relic here.
	;all the needs are met for the expression in CAR(R2)
	MOV	CAR(R2),R1	;R1 ← expression node
6$:	CALL	EVALND,<R1,EVL.T(RF)>	;Evaluate the expression.
	MOV	EVL.ND(RF),R0	;R0 ← target node
	MOV	GNVAL(R1),GNVAL(R0)	;Stow away its new value.
⊗

7$:	CLR	INVMRK(R0)	;Mark it as valid.
	INC	VALIDF(R0)	;Increment its validity number
8$:	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
9$:	RTS	PC		;Done

COMMENT ⊗ Each expression has a field, ENISB, which points to the
interpreter status block of its definition.  This contains enough
information to resolve any variable references in the expression.
Calls the interpreter in a special way (through a pseudo-CALL INTERP) having
first set up a pseudo-ISB in R4.  When the interpreter returns, the
desired value should be in R0.  Each time called, this routine
constructs a new pseudo-ISB, uses it once, and then releases it.
This is somewhat wasteful, and could be cleaned up.  The value found
is put in the expression node, which is marked as valid.  It is not
assumed that all the needed nodes have been validated before this
routine is called.  ⊗

ROUTINE EVLEXP,<EVE.EXP,EVE.T>
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	R4,-(SP)	;Save R4

	;try to validate the needed list
	MOV	EVE.EXP(RF),R0	;R0 ← LOC[ENODE]
	MOV	EVE.T(RF),INVMRK(R0)	;We are looking now.
	MOV	ENNEED(R0),R3	;R3 ← needed list
	BEQ	2$		;if any
1$:	CALL	EVALND,<CAR(R3),EVE.T(RF)>	;Evaluate this need.
	MOV	CAR(R3),R0	;R0 ← variable node of the need
	TST	INVMRK(R0)	;Is it now valid?
	BNE	3$		;No, so we fail
	MOV	CDR(R3),R3	;Yes.  R3 ← next needed cell
	BNE	1$		;If any.

	;the needed list is ready
2$:	MOV	#ISBS,R0	;Get a pseudo-ISB
	JSR	PC,GTFREE	;R0 ← LOC[new ISB]
	MOV	R0,R4		;R4 ← LOC[new ISB]
	MOV	EVE.EXP(RF),R2	;
	MOV	ENISB(R2),R1	;R1 ← LOC[old ISB]
	MOV	ENV(R1),ENV(R4)	;Copy environments
	MOV	LEV(R1),LEV(R4)	;Copy levels
	MOV	ENIPC(R2),IPC(R4)	;Initialize the IPC
	MOV	#INSTSZ,R0	;
	JSR	PC,GTFREE	;R0 ← LOC[new interpreter stack]
	MOV	R0,-(SP)	;Save the stack location
	ADD	#2*INSTSZ,R0	;
	MOV	R0,R3		;R3 ← LOC[verge of new interpreter stack]
 	JSR	PC,NOGC		;Don't garbage collect during this.
	MOV	RF,-(SP)	;Save RF
	MOV	SP,RF
	JSR	PC,INTERP	;Enter the interpreter, R0 ← LOC[new value cell]
	MOV	EVE.EXP(RF),R2	;R0 ← LOC[expression node]
	CLR	INVMRK(R2)	;Now valid
	MOV	R0,GNVAL(R2)	;Result into the node
	MOV	R4,R0		;Release the ISB
	JSR	PC,RLFREE	;
	MOV	(SP)+,R0	;Release the interpreter stack
	JSR	PC,RLFREE	;
	JSR	PC,YESGC	;Garbage collect ok now.
3$:	MOV	(SP)+,R4	;Restore R4
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	PC		;Return
;  MAKEXP, ADDCLC, REMCLC, DELEXP

ROUTINE ADDCLC,<ADD.VN,ADD.EN>
COMMENT ⊗ ADD.VN is the variable node, and ADD.EN is an expression
node all prepared except for the link to the variable node.  This
linking is performed.  ⊗
⊗
	MOV	R2,-(SP)	;Save R2
	MOV	R3,-(SP)	;Save R3
	MOV	ADD.VN(RF),R2	;R2 ← LOC[variable node]
	MOV	ADD.EN(RF),R3	;R3 ← LOC[expression node]
	EVWAIT	GNEVT		;Enter critical region
	;Add the VNODE as a dependent of the ENODE
	JSR	PC,NEWCEL	;R0 ← LOC[new cell]
	MOV	GNDEPS(R3),CDR(R0)
	MOV	R2,CAR(R0)	;
	MOV	R0,GNDEPS(R3)	;
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	;Add the ENODE as an expression of the VNODE
	JSR	PC,NEWCEL	;R0 ← LOC[new cell]
	MOV	VNCLCS(R2),CDR(R0)
	MOV	R3,CAR(R0)	;
	MOV	R0,VNCLCS(R2)	;
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	EVSIG	GNEVT		;Leave critical region
	MOV	(SP)+,R3	;Restore R3
	MOV	(SP)+,R2	;Restore R2
	RTS	PC		;Done

ROUTINE MAKEXP,<MKE.ISB,MKE.IPC,MKE.NDS>
COMMENT ⊗ Makes a new expression node with ENISB, ENIPC, ENNDS as
specified.  Makes it a dependent of all the variables on the needed
list.  ⊗

	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV #ENDSIZ,R0		;
	JSR PC,GTFREE		;
	MOV R0,R3		;R3 ← LOC[new expression node]
	MOV #2,GNMODE(R3)	;Expression
	MOV #-1,INVMRK(R3)	;Invalid
	CLR GNVAL(R3)		;No value
	CLR GNDEPS(R3)		;No variable dependents
	MOV MKE.ISB(RF),ENISB(R3)	;ISB
	MOV MKE.IPC(RF),ENIPC(R3)	;IPC
	MOV MKE.NDS(RF),R2	;Need list
	EVWAIT GNEVT		;Enter critical region
	MOV R2,ENNEED(R3)	;

	;this expression is a dependent for each variable on the needed list.
	BEQ 2$			;If any
1$:	JSR PC,NEWCEL		;
	MOV CAR(R2),R1		;R1 ← the next needed variable
	MOV GNDEPS(R1),CDR(R0)	;
	MOV R3,CAR(R0)		;
	MOV R0,GNDEPS(R1)
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	MOV CDR(R2),R2		;
	BNE 1$			;Repeat

2$:	;link up with all other graph nodes in the world
	MOV GNODES,R1		;
	BEQ 3$			;If any
	MOV R1,NXTGN(R3)	;
	MOV R3,PRVGN(R1)	;
3$:	MOV R3,GNODES		;
	MOV R3,R0		;R0 ← LOC[new expression node]
	EVSIG GNEVT		;Leave critical region
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done

ROUTINE REMCLC,<RMC.VN,RMC.EN>
COMMENT ⊗ Unlinks the given expression from the given variable.  ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV RMC.EN(RF),R2	;R2 ← ENODE
	MOV RMC.VN(RF),R3	;R3 ← VNODE
	CALL GETVAL,<R3>	;Make sure he has a last chance to get value.
	EVSIG GNEVT		;Enter critical region
	;remove the VNODE as a dependent of the ENODE
	MOV GNDEPS(R2),R0	;
	MOV R3,R1		;
	JSR PC,UNLINK		;
	MOV R0,GNDEPS(R2)	;
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	;remove the ENODE as a calculator of the VNODE
	MOV VNCLCS(R3),R0	;
	MOV R2,R1		;
	JSR PC,UNLINK		;
	MOV R0,VNCLCS(R3)	;
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	EVSIG GNEVT		;Leave critical region
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done

ROUTINE DELEXP,<DLE.EN>
COMMENT ⊗ Must remove this expression from all variable nodes which
are dependent on it, having tried to validate them.  Then unlink the
expression node and reclaim it. modified 10/76 by arg ⊗
	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV DLE.EN(RF),R2	;R2 ← LOC[victim expression node]
	EVWAIT GNEVT		;Enter critical region
	MOV GNDEPS(R2),R3	;R3 ← list of dependents
	BEQ 2$			;If any
	JSR PC,NXTTIM		;
	MOV R0,-(SP)		;New time for the evaluations to follow
1$:	MOV CAR(R3),R0		;
	MOV (SP),R1		;Time
	CALL EVALND,<R0,R1>	;Try to validate him
	MOV VNCLCS(R0),R0	;R0 ← his list of calculators
	MOV R2,R1		;us
	JSR PC,UNLINK		;Remove us from that list
	MOV CAR(R3),R1		;him
	MOV R0,VNCLCS(R1)	;Put back his calculator list, minus us.
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	MOV CDR(R3),R3		;Next calculator
	BNE 1$			;If any
	TST (SP)+		;Clear the time from the stack

	;Remove the expression from the dependent list's of all the variables
	;on the expressions needed list
2$:	MOV ENNEED(R2),R3	;Get needed list
	BEQ 4$			;If any
3$:	MOV CAR(R3),R0		;R0 ← variable from needed list
	MOV GNDEPS(R0),R0	;R0 ← his list of dependents
	MOV R2,R1		;us
	JSR PC,UNLINK		;Remove us from his list
	MOV CAR(R3),R1		;him again
	MOV R0,GNDEPS(R1)	;Put back his dependent list minus us
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	MOV CDR(R3),R3		;Next from needed list
	BNE 3$			;Til done

	;unlink this expression node
4$:	MOV NXTGN(R2),R1	;R1 ← forward link
	MOV PRVGN(R2),R0	;R0 ← backward link
	MOV R0,PRVGN(R1)	;
	MOV R1,NXTGN(R0)	;
	MOV R2,R0
	JSR PC,RLFREE		;Release the space
	EVSIG GNEVT		;Leave critical region.
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done
	
;  MAKEVN, DELVN

MAKEVN:
COMMENT ⊗ Creates a variable node, with no frills (no calculators,
changers, loksh, boydem, tsibele, ...) except that if R0 is
non-zero, that is assumed to be the value cell pointer.  The node
will be marked as invalid unless there was some value given.  The
space is taken from large block storage.  The new variable node is
returned in R0.  ⊗

	MOV R0,-(SP)		;Save R0
	MOV #VNDSIZ,R0
	JSR PC,GTFREE		;R0 ← LOC[new graph node]
	CLR INVMRK(R0)		;Validate the node
	MOV #1,GNMODE(R0)	;Variable, not expression
	MOV (SP)+,GNVAL(R0)	;Stuff away the value cell pointer.
	BNE 1$			;Was there one?
	MOV #-1,INVMRK(R0)	;No. Invalidate this node.
1$:	CLR GNDEPS(R0)		;Zero other fields
	CLR VNCLCS(R0)	
	CLR VNCHGS(R0)
	CLR NXTGN(R0)
	CLR PRVGN(R0)
	CLR VALIDF(R0)
	EVWAIT GNEVT		;Critical section here
	MOV GNODES,R1		;Link up to other nodes in the world.
	BEQ 2$			;If any
	MOV R1,NXTGN(R0)
	MOV R0,PRVGN(R1)
2$:	MOV R0,GNODES	
	EVSIG GNEVT		;End of critical section
	RTS PC

DELVN:
COMMENT ⊗ R0 is the location of the variable node.  All dependent
expressions are first validated if possible, then those are deleted.
(Not any more. arg 10/76)
The value cell and all cell lists (like GNDEPS, VNCLCS) are reclaimed
by relying on the garbage colector.  Thus graph nodes may share value
cells.  The changer list is explicitly released, so changer lists may
not be shared.  Then the node itself is unlinked from the chain and
returned to free storage. ⊗

	MOV R2,-(SP)		;Save R2
	MOV R3,-(SP)		;Save R3
	MOV R0,R2		;R2 ← variable node to delete

	;Try to validate the dependents
	MOV GNDEPS(R2),R3	;R3 ← List of dependent expressions
	BEQ 2$			;if any
1$:	CALL DELEXP,<CAR(R3)>	;Delete expression.
	MOV CDR(R3),R3		;R3 ← next dependent
	BNE 1$			;if any

	;Tell each calculator expression that we are no longer dependent
2$:	EVWAIT GNEVT		;Enter critical region
	MOV VNCLCS(R2),R3	;R3 ← List of calculator expressions
	BEQ 5$			;If any
3$:	MOV CAR(R3),R0		;
	MOV GNDEPS(R0),R0	;R0 ← that expression's dependent list
	MOV R2,R1		;R1 ← us
	JSR PC,UNLINK		;Remove us from his dependent list
	MOV CAR(R3),R1		;R1 ← him
	MOV R0,GNDEPS(R1)	;Replace his new dependent list
   .IFNZ SMALLB
	EVSIG SBEVT	;End of critical section - value stored
   .ENDC
	BNE 4$
	CALL DELEXP,<R1>	;Delete expression if no one else dependent on him
4$:	MOV CDR(R3),R3		;Do the same for the other calculator expressions
	BNE 3$			;If any

	;Reclaim the changer cells
5$:	MOV VNCHGS(R2),R3	;R3 ← First changer cell
6$::	MOV R3,R0		;R0 ← current changer cell
	BEQ 7$			;If any
	MOV NXTCHG(R3),R3	;R3 ← next changer cell
	JSR PC,RLFREE		;Release current one
	BR  6$			;Do the others

	;Unlink this graph node
7$:	MOV NXTGN(R2),R1	;R1 ← forward link
	MOV PRVGN(R2),R0	;R0 ← backward link
	BEQ 8$			;if any
	MOV R1,NXTGN(R0)	;
	BR 9$			;
8$:	MOV R1,GNODES		;if no backward link, then the header.
9$:	TST R1			;Is there a forward link?
	BEQ 10$			;No
	MOV R0,PRVGN(R1)	;Yes.  set up next guy's backpointer
10$:	EVSIG GNEVT		;Leave critical region.

	MOV R2,R0		;R0 ← target graph node hulk
	JSR PC,RLFREE		;Release it.
	MOV (SP)+,R3		;Restore R3
	MOV (SP)+,R2		;Restore R2
	RTS PC			;Done

;  MGNDS  marking method for gnodes

MGNDS:	;Marking method for GNODES
	MOV R2,-(SP)		;Save R2
	EVWAIT GNEVT		;Enter critical region
	MOV GNODES,R2		;R2 ← LOC[first graph node]
	BEQ 4$			;If none, then done
1$:	TST INVMRK(R2)		;See if value is valid
	BEQ 5$
	CLR GNVAL(R2)		; & if so don't mark it
	BR  6$
5$:	MOV GNVAL(R2),R0	;Mark the value cell
	JSR PC,MARKQ		;
	MOV R0,GNVAL(R2)	;Put it back (compacting may move it)
6$:	MOV GNDEPS(R2),R0	;Mark the cells used in the dependent list
	JSR PC,MCELL		;
	MOV R0,GNDEPS(R2)	;Put it back
	BIT #1,GNMODE(R2)	;What kind of graph node is it?
	BEQ 2$
	MOV VNCLCS(R2),R0	;A variable.  Mark cells in CLC list
	JSR PC,MCELL		;
	MOV R0,VNCLCS(R2)	;Put it back
	BR  3$
2$:	MOV ENNEED(R2),R0	;An expression.   Mark cells in ENNEED list
	JSR PC,MCELL		;
	MOV R0,ENNEED(R2)	;Put it back
3$:	MOV NXTGN(R2),R2	;R2 ← LOC[next graph node]
	BNE 1$			;Repeat as necessary
4$:	MOV (SP)+,R2		;Restore R2
	EVSIG GNEVT		;Leave critical region
	RTS PC			;Return
;  Known Bugs

COMMENT ⊗ It is possible that while a graph node is changed, a
changer is invoked.  During its execution, some other process
modifies the change list for that node.  When the changer is done, it
may get lost in the changer cell list.  Graph node exclusion must be
turned off during execution of a changer, so that it can change other
cells.  Special changer exclusion causes deadlock in the case that
one changer triggers another.  

Certain variables, like YELLOW and BLUE, are not being initialized
to anything.

⊗